package 蓝桥杯算法;


import 二叉树.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class day27 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(3),
                        2,
                        new TreeNode(0)
                ),
                3,
                new TreeNode(
                        new TreeNode(1),
                        3,
                        new TreeNode(0)
                )
        );
        day27 d = new day27();
        System.out.println(d.rob1(root));
        int[] num = {7, 1, 5, 3, 6, 4};
        System.out.println(d.max(num));
        System.out.println(d.maxprice(num));
        System.out.println(d.maxprice1(num));
        int[] price={3,3,5,0,0,3,1,4};
        System.out.println(d.maxprice2(price));
        int[] price3={2,4,1};
        System.out.println(d.maxprice3(price3,2));

    }

    public int rob1(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>();
        return robAction(root, memo);
    }

    public int robAction(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        int money = root.val;
        if (root.left != null) {//此处隔离了一层
            money += robAction(root.left.left, map) + robAction(root.left.right, map);
        }
        if (root.right != null) {
            money += robAction(root.right.left, map) + robAction(root.right.right, map);
        }
        int res = Math.max(money, robAction(root.left, map) + robAction(root.right, map));
        map.put(root, res);//完成这步操作，会把相关的东西存入
        return res;
    }

    public int max(int[] num) {
        int[] dp = new int[num.length];
        int max = 0;
        max = Integer.MIN_VALUE;
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j < num.length; j++) {
                max = Math.max(max, num[j] - num[i]);
            }
        }
        return max;
    }

    public int maxprice(int[] price) {//买卖股票用二重数组
        if (price == null || price.length == 0) {
            return 0;
        }
        int[][] dp = new int[price.length][2];
        dp[0][0] = -price[0];//买入股票花的最少的钱
        dp[0][1] = 0;//卖出股票赚的最多的钱
        for (int i = 1; i < price.length; i++) {
            //选出损失最小的
            dp[i][0] = Math.max(dp[i - 1][0], -price[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + price[i], dp[i - 1][1]);
        }
        return dp[price.length - 1][1];
    }

    public int maxprice1(int[] price) {
        if (price == null || price.length == 0) {
            return 0;
        }
        int[][] dp = new int[price.length][2];
        dp[0][0] = -price[0];
        dp[0][1] = 0;
        int result = 0;
        for (int i = 1; i < price.length; i++) {
            //持有股票
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - price[i]);
            //卖出股票
            dp[i][1] = Math.max(dp[i - 1][0] + price[i], dp[i - 1][1]);
        }
        return dp[price.length - 1][1];
    }

    public int maxprice2(int[] price) {
        if (price == null || price.length == 0) {
            return 0;
        }
        int[][] dp=new int[price.length][5];
        //未卖出
        dp[0][1]=-price[0];
        dp[0][3]=-price[0];
        for(int i=1;i<price.length;i++){
            //每次循环都有相应的四个阶段
            dp[i][1]=Math.max(dp[i-1][1],-price[i]);
            //上一次的结果，与这次的卖出
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]+price[i]);
            //新的买入
            dp[i][3]=Math.max(dp[i-1][3],dp[i-1][2]-price[i]);
            //新的卖出
            dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]+price[i]);

        }
        return dp[price.length-1][4];
    }
    public int maxprice3(int[] price,int k){
        if(price==null||price.length==0){
            return 0;
        }
        int[][][]dp=new int[price.length][k+1][2];
        for(int i=0;i<=k;i++){
            dp[0][i][1]=-price[0];
        }

        for(int i=1;i<price.length;i++){
            for(int j=1;j<=k;j++){
                //新的买入
                dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+price[i]);
                //上一次的买入，上一次的卖出加这次的买入
                //新的卖出
                dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-price[i]);
                //上一次的卖出，上一次的卖出(上个k次的卖出-买入

            }
        }
        return dp[price.length-1][k][0];


    }

}

